#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/17 12:09
# @USER    : Shengji He
# @File    : WildcardMatching.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def __init__(self):
        self.dp = {}

    def remove_duplicate_stars(self, p):
        if p == '':
            return p
        p1 = [p[0],]
        for element in p[1:]:
            if p1[-1] != '*' or p1[-1] == '*' and element != '*':
                p1.append(element)
        return ''.join(p1)

    def helper(self, s, p):
        dp = self.dp
        if (s, p) in dp:
            return dp[(s, p)]

        if p == s or p == '*':
            dp[(s, p)] = True
        elif p == '' or s == '':
            dp[(s, p)] = False
        elif p[0] == s[0] or p[0] == '?':
            dp[(s, p)] = self.helper(s[1:], p[1:])
        elif p[0] == '*':
            dp[(s, p)] = self.helper(s, p[1:]) or self.helper(s[1:], p)
        else:
            dp[(s, p)] = False
        return dp[(s, p)]

    def isMatch(self, s: str, p: str) -> bool:
        """
        Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

        - '?' Matches any single character.
        - '*' Matches any sequence of characters (including the empty sequence).

        The matching should cover the entire input string (not partial).

        Note:
            - s could be empty and contains only lowercase letters a-z.
            - p could be empty and contains only lowercase letters a-z, and characters like ? or *.
        Example 1:
            Input:
                s = "aa"

                p = "a"
            Output: false

            Explanation: "a" does not match the entire string "aa".
        Example 2:
            Input:
                s = "aa"

                p = "*"
            Output: true

            Explanation: '*' matches any sequence.
        Example 3:
            Input:
                s = "cb"

                p = "?a"

            Output: false

            Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
        Example 4:
            Input:
                s = "adceb"

                p = "*a*b"
            Output: true

            Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
        Example 5:
            Input:
                s = "acdcb"

                p = "a*c?b"
            Output: false

        :param s:
        :param p:
        :return:
        """
        # p = self.remove_duplicate_stars(p)
        # return self.helper(s, p)

        # way 2
        # p = self.remove_duplicate_stars(p)
        s_len, p_len = len(s), len(p)
        s_idx = p_idx = 0
        star_idx = s_tmp_idx = -1
        while s_idx < s_len:
            if p_idx < p_len and p[p_idx] in ['?', s[s_idx]]:
                s_idx += 1
                p_idx += 1
            elif p_idx < p_len and p[p_idx] == '*':
                star_idx = p_idx
                s_tmp_idx = s_idx
                p_idx += 1
            elif star_idx == -1:
                return False
            else:
                p_idx = star_idx + 1
                s_idx = s_tmp_idx + 1
                s_tmp_idx = s_idx
        return all(x == '*' for x in p[p_idx:])



if __name__ == '__main__':
    S = Solution()
    # s = 'abcdefgh'
    # p = 'a*de*h'
    # s = "aaaa"
    # p = "***a"
    s = "aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba"
    p = "a*******b"
    print(S.isMatch(s, p))
    print('done')
